Định lý Kuratowski[4][5] liên quan giữa tính phẳng của đồ thị và K 3 , 3 {\displaystyle K_{3,3}} : Điều kiện cần và đủ một đồ thị liên thông G có tính phẳng là G không chứa bất kỳ đồ thị con nào đồng phôi với K 5 {\displaystyle K_{5}} hay K 3 , 3 {\displaystyle K_{3,3}} . Đồ thị K 3 , 3 {\displaystyle K_{3,3}} là đồ thị không phẳng có ít cạnh nhất.
K3,3 và K5
Một đồ thị hai phía đầy đủ K m , n {\displaystyle K_{m,n}} có số phủ đỉnh (Vertex covering number) bằng min { m , n } {\displaystyle \min \lbrace m,n\rbrace } và số phủ cạnh (Edge covering number) bằng max { m , n } {\displaystyle \max \lbrace m,n\rbrace }
Đồ thị hai phía đầy đủ K 4 , 4 {\displaystyle K_{4,4}} là một Cayley Graph.[6]
Một đồ thị đủ K n {\displaystyle K_{n}} có thể được tách thành 4 đồ thị con, mỗi đồ thị con là một đồ thị hai phía đầy đủ, H 1 {\displaystyle H_{1}} , H 2 {\displaystyle H_{2}} , H 3 {\displaystyle H_{3}} ,... H m {\displaystyle H_{m}} , sao cho m ≥ n − 1 {\displaystyle m\geq \;n-1} [7]
K5 to 4cbg
Đồ thị hai phía đầy đủ K m , n {\displaystyle K_{m,n}} là k-choosable khi và chỉ khi n < m m {\displaystyle n<\;m^{m}} [8]
Một đồ thị hai phía đầy đủ K m , n {\displaystyle K_{m,n}} có cặp ghép hoàn hảo (Perfect matching) kích thước min { m , n } {\displaystyle \min \lbrace m,n\rbrace }
Một đồ thị hai phía đầy đủ K n , n {\displaystyle K_{n,n}} hay K n , n + 1 {\displaystyle K_{n,n+1}} là một đồ thị Turán.[9]
Một đồ thị hai phía đầy đủ K m , n {\displaystyle K_{m,n}} có mn−1 nm−1 cây bao trùm
Ma trận Laplace của đồ thị hai phía đầy đủ K m , n {\displaystyle K_{m,n}} có các vectơ n+m, n, m, 0; với các vectơ tương thích 1, m-1, n-1, 1.
Một đồ thị hai phía đầy đủ K n , n {\displaystyle K_{n,n}} có một cách tô màu cạnh (Edge coloring) đúng đắn, n_Edge = n_color.[10]
Sắc số của đồ thị K m , n {\displaystyle K_{m,n}} là 2 [11].
Số màu cần thiết để tô màu các cạnh của K m , n {\displaystyle K_{m,n}} là max{m.n} để không có 2 cạnh nào cùng màu mà lại có chung đỉnh.
Đường kính của đồ thị hai phía đầy đủ: K 1 , 1 {\displaystyle K_{1,1}} là 1, còn tất cả các K m , n {\displaystyle K_{m,n}} khác đều có đường kính là 2.[12]
